package airthmetic.exercise.heap;

import java.util.PriorityQueue;

public class _703_数据流中的第K大元素 {
    static class KthLargest {
        private int k;
        private PriorityQueue<Integer> priorityQueue;
        public KthLargest(int k, int[] nums) {
            this.k = k;
            this.priorityQueue = new PriorityQueue<>(k);
            for(int i=0; i< nums.length; i++){
                add(nums[i]);
            }
        }


        public int add(int val) {
            if(priorityQueue.size() < k){
                priorityQueue.offer(val);
            }else{
                if(priorityQueue.peek() < val){
                    priorityQueue.poll();
                    priorityQueue.offer(val);
                }
            }
            return priorityQueue.peek();
        }

        // 错误的自己写的方法
        // 错误在于对于优先级队列的理解不够深,
        // 这种写法，如果达到优先级队列的长度，但是新入队的元素没有大于堆顶的最小元素，此时不会进入if，
        // 也就是说不会出队，最终还会把最新元素入队,破坏了队列元素数量
        // 也就是说，如果堆满了，再来的元素小于堆顶的最小元素，此时不应出堆和入堆
       /* public int add(int val) {
            if(priorityQueue.size() >= k && priorityQueue.peek() < val){
                priorityQueue.poll();
            }
            priorityQueue.offer(val);
            return priorityQueue.peek();
        }*/

    }

    public static void main(String[] args) {
        KthLargest kthLargest = new KthLargest(3, new int[]{4, 5, 8, 2});
        System.out.println(kthLargest);
        kthLargest.add(3);
        kthLargest.add(5);
        kthLargest.add(10);
        kthLargest.add(9);
        kthLargest.add(4);

    }
}
